package demo2;

import demo1.TestDemo;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-12
 * Time: 7:47
 */
public class TestDemo1 {
    // 给定一棵二叉树的头节点head，任何两个节点之间都存在距离，返回整棵二叉树的最大距离

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }
    //左树的最大距离
    //右树的最大距离
    //左树高度+右树高度+1

    static class Info{
        public int max;
        public int height;

        public Info(int max,int height){
            this.max = max;
            this.height = height;
        }
    }

    //左树的最大距离
    //右树的最大距离
    //左树高度+右树高度+1
    public static Info process(TreeNode x){
        if(x==null) return new Info(0,0);
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height,rightInfo.height) +1;
        int max = Math.max(leftInfo.max,
                Math.max(rightInfo.max,leftInfo.height+ rightInfo.height +1));
        return new Info(max,height);
    }


    public static int maxDistance(TreeNode head){
          return process(head).max;
    }



}
